package com.kzc.twelve.alg;

import java.util.ArrayList;
import java.util.List;

/**
 * 一个路径查找器
 * Created by 柯尊诚 on 2015/12/9.
 * kzc
 */
public class AstarPathFinder {

    public static List<Location> findPath(Location start, Location dest, int[][] map) {
        ArrayList<Location> openList = new ArrayList<>();
        ArrayList<Location> closeList = new ArrayList<>();

        List<Location> path = new ArrayList<>();
        openList.add(start);
        Location current = null;

        do {
            current = getLowestFscoreLocation(openList);
            closeList.add(current);
            openList.remove(current);

            if (closeList.contains(dest)) {
                break;
            }

            List<Location> adjacentLocations = getWalkableAdjacentLocations(current, map);

            for (Location lo : adjacentLocations) {
                if (closeList.contains(lo)) {
                    continue;
                }
                if (!openList.contains(lo)) {
                    lo.setMovedSteps(current.getMovedSteps() + 1);
                    lo.setEvalRemainSteps(evalRemainSteps(current, dest));
                    lo.setTotalEvalSteps(evalRemainSteps(current, dest) + lo.getMovedSteps());
                    openList.add(lo);

                } else {
                    if (current.getMovedSteps() + 1 < lo.getMovedSteps()) {
                        lo.setMovedSteps(current.getMovedSteps() + 1);
                        lo.setPrevious(current);
                    }
                }

            }
        } while (!openList.isEmpty());

        Location destination = null;
        if (closeList.contains(dest)) {
            destination = current;
            path.add(destination);
            while (destination.getPrevious() != null) {
                destination = destination.getPrevious();
                path.add(destination);
            }
        }

        return path;
    }

    private static List<Location> getWalkableAdjacentLocations(Location current, int[][] map) {
        int x = current.getX();
        int y = current.getY();

        List<Location> walkableLos = new ArrayList<>();
        Location lo = null;

        if (x + 1 < map[0].length && map[y][x + 1] == 1) {
            lo = new Location(x + 1, y);
            lo.setPrevious(current);
            walkableLos.add(lo);
        }

        if (x - 1 >= 0 && map[y][x - 1] == 1) {
            lo = new Location(x - 1, y);
            lo.setPrevious(current);
            walkableLos.add(lo);
        }

        if (y + 1 < map.length && map[y + 1][x] == 1) {
            lo = new Location(x, y + 1);
            lo.setPrevious(current);
            walkableLos.add(lo);
        }

        if (y - 1 >= 0 && map[y - 1][x] == 1) {
            lo = new Location(x, y - 1);
            lo.setPrevious(current);
            walkableLos.add(lo);
        }

        return walkableLos;
    }

    private static Location getLowestFscoreLocation(List<Location> openList) {
        if (openList == null || openList.size() == 0) {
            return null;
        }

        int minSteps = openList.get(0).getTotalEvalSteps();
        int tmpSteps = 0;
        Location lowesFlocation = openList.get(0);

        for (Location lo : openList) {
            tmpSteps = lo.getTotalEvalSteps();
            if (tmpSteps < minSteps) {
                minSteps = tmpSteps;
                lowesFlocation = lo;
            }
        }

        return lowesFlocation;
    }


    private static int evalRemainSteps(Location current, Location dest) {
        int distanceX = dest.getX() - current.getX();
        int distanceY = dest.getY() - current.getY();

        if (distanceX < 0) {
            distanceX = distanceX * -1;
        }

        if (distanceY < 0) {
            distanceY = distanceY * -1;
        }

        return distanceX + distanceY;
    }


}
